package com.demo.dsa;

public class 多项式 {

  /**
   * f(x) = 1 + x + x^2/2 + x^i/i + x^100/100
   */
  public static void main(String[] args) {
    int n = 1000;
    double a[] = new double[n];
    a[0] = 1;
    for (int i = 1; i < a.length; i++) {
      a[i] = 1.0 / i;
    }
    long beginTime = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
      f1(n, a, 1.1);
    }
    System.out.println(System.currentTimeMillis() - beginTime);
    System.out.println("====");
    long beginTime2 = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
      f2(n, a, 1.1);
    }
    System.out.println(System.currentTimeMillis() - beginTime2);
  }

  // 普通方法
  public static double f1(int n,double a[], double x) {
    double res = 0;
    for (int i = 0; i < n; i++) {
      res  = res + Math.pow(x, i) * a[i];
    }
    return res;
  }

  // f(x) = 1 + x(1 + x(1/2 +...+ x(1/100)))
  public static double f2(int n,double a[], double x) {
    double res = a[n - 1];
    for (int i = n - 1; i > 0; i--) {
      res = a[i - 1] + x * res;
    }
    return res;
  }
}
